class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        m = {}
        ha = headA
        m[ha] = 1
        while ha:
            ha = ha.next
            m[ha] = 1
        hb = headB
        while hb:
            if hb in m:
                return hb
            hb = hb.next
        return hb

    def getIntersectionNode2(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        ha = headA
        hb = headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha



